import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-08-15
 * Time: 20:19
 */
//https://leetcode.cn/problems/valid-triangle-number/submissions/653379845/
public class Test {
    public static int triangleNumber(int[] arr) {
        int size=arr.length;
        if(size<3){
            return 0;
        }
        Arrays.sort(arr);
        int i,j,k,jj,m,n=0;
        for( i=0;i<arr.length-2;i++){
            if(arr[i]*2>arr[size-1]){
                n+=(size-i)*(size-i-1)*(size-i-2)/6;
                i=size;
                break;
            }
            for( j=i+1,jj=i+1;j<size-1;j++){
                m=arr[i]+arr[j];
                if(m>arr[size-1]){
                    n+=(size-j)*(size-j-1)/2;
                    j=size;
                    break;
                }
                if(jj>j+1){
                    k=jj;
                    n+=jj-j-1;
                }
                else{
                    k=j+1;
                }
                for( ;k<size;k++){
                    if(arr[k]<m){
                        n++;
                    }
                    else{
                        break;
                    }
                }
                jj=k;
            }
        }
        return n;
    }
    public static void main(String[] args) {
        int[] arr={2,2,3,4};
        System.out.println(triangleNumber(arr));
    }
}
